本來想棄賽了，立了一個Flag，如果明天也放假的話就繼續寫...
所以只好再撐一天了，是說放公式也太麻煩了吧...
今天來介紹一些MCTS的優化方式，或是一些針對不同遊戲的策略改進。
我們再看一下 MCTS 的四個步驟，昨天著重於Selection的部分，畢竟如何選點真的影響非常大，今天也會介紹到其他階段的優化。
Simulated Annealing (模擬退火法)也是用來平衡 exploration 與 exploitation 的一種方式，透過一個「溫度常數」（temperature constant, K）來調整節點選擇時的隨機性。具體做法是在進行模擬過程中，根據分數與當前節點的差異來決定挑選節點的機率，而溫度常數 K 控制了這個過程中的隨機程度。
選擇不同節點的機率：
這表示節點 被選中的機率與它的分數
以及溫度常數 K 有關。當 K = 0 時，所有節點被選中的機率是均等的（即隨機選擇），而當 K 增加時，分數較高的節點被選中的機率也會隨之上升。
模擬退火法通過逐漸降低 K 值，使演算法從初期的隨機探索逐漸轉向更專注於高分節點的探索。這有助於在早期保持廣泛的探索，避免陷入局部最優，隨後集中在最有潛力的路徑上。
AMAF (手順不羈法)，其目的是在模擬結束後(進入Backpropagation)，除了更新當前經過的節點外，還更新該節點的其他同級節點，以充分利用模擬中的資訊。這樣做雖然會引入偏差，但能加速樹的成長，並提高演算法對於勝率的信心。
某些走步的價值不一定會因為執行的具體時機不同而有太大的變化。因此，即便某個動作沒有立即執行，它的效益可以被用來更新目前的估值。具體而言，在一次模擬中，所有參與過的動作都可以被視作是「第一個動作」來更新其評估值。
這邊我們用五子棋當範例來看，黑棋下在 A，就會勝利。
然而黑棋想皮一下先下在 X，那也不影響他的勝利，所以 AMAF 模擬到 A 這步時也同時更新同級其他節點的分數。
由於一次模擬的結果可以同時更新多個節點，AMAF 主要的優勢在於它可以讓模擬的收斂速度加快，可以有效提升效能。
但是有時候手順也是很重要的，我們再來看看上面的範例，如果黑棋是下在其他毫不相干的地方呢？
白棋下一手一定會去擋在 A 點的，所以這種時候模擬的品質就不是很好。
還有比如圍棋中的打劫，手順不對有時候還是犯規的，又或是象棋、圍棋一些詰棋，手順就非常的重要，次序錯了就無法獲勝，然而 AMAF 並不在意這些次序，尤其在終盤時表現會較差，犧牲了一些模擬品質，但速度更快。
RAVE (模擬數值快速更新法)，為AMAF的改良版本，或者說折衷版本。
RAVE 將兩種評估方式結合：
RAVE 會將這兩個估值進行加權合併：
其中 是依據經驗確定的參數，並隨著模擬次數的增加而動態調整。
等於0的時候其實就是 AMAF ，當節點被模擬的次數越多，
愈趨近於 1，這表示愈依賴傳統的 MCTS 評估方法，而當模擬次數較少時，則更多依賴 RAVE 的快速估值。
這樣的設計可以在模擬初期快速得到節點的估值，而隨著模擬次數增加，演算法會更傾向於依賴傳統的模擬結果。這種方法加速了 MCTS 的搜索過程，使得演算法在有限的時間內能夠更快地收斂到較好的決策。
在 MCTS 的節點展開階段，優化展開策略也可以顯著提升搜索效率和決策質量，比如每次經過Selection選擇的節點，都對其作全展開(展開所有合法走步)，這樣效率就會比較差。
快贏策略，如同字面上的意思，就是想要快速的獲得勝利。
下圖為 Breakthrough 遊戲，下圖黑棋只需要移動藍框中的棋子即可獲得勝利，但由於上方黃框中的黑棋有機會吃子，平均勝率會比下方來得更高，雖然黑棋一樣會獲得勝利，卻也延後了獲勝的時間。
圖片來源：AlphaZero演算法結合快贏策略或迫著空間實現於五子棋
其實跟上面 AMAF 的五子棋例子有點像，總之我們當然希望能愈快贏得遊戲愈好。
這邊論文中提到在 Backpropagation 階段中更新值時針對已知勝負的節點加上一個 V 值，這樣能夠更快地找到勝利的走步，並傾向於選擇能加速勝利的行動。
原始 UCT 公式：
改動後的 UCT 公式（加入 Quick Win 方法的 V 值加權）：
當節點的 V 值為 1 或 -1（即已知勝負）時，根據深度差 進行加權，修改後的公式為：
其中， 是加權後的獎勵值，定義如下：
參數說明：
大贏策略，有時候我們不只是追求贏更要追求大勝，如何贏得更多就是一個需要思考的問題了，比如2017時，很多根據 AlphaGo 論文實作出來的圍棋AI程式，都有個問題，就是在官子階段會有退讓的情況，並不會追求完美的獲勝。
iThome鐵人賽
看影片追技術